//https://www.bilibili.com/video/BV1d54y1f7B3?spm_id_from=333.788.videopod.episodes&vd_source=d6fe65f095f01f05591e89d810720ccc&p=20
// 2024-10-22

import java.util.LinkedList;
import java.util.Queue;

public class P028_省份数量_并查集 {

    public static void main(String[] args) {
        System.out.println(mergeFind(new int[][] {{1,1,0},{1,1,0},{0,0,1}}));
//        System.out.println(fun(new int[][] {5,5,5,20}));
    }

    //并查集
    private static int mergeFind(int[][] citysConnexted) {
        int citys = citysConnexted.length;
        int[] head = new int[citys];//每个节点的头节点
        int[] level = new int[citys];//层高
        for (int i = 0; i < citys; i++) {
            head[i] = i;
            level[i] = 1;//初始化
        }

        //遍历矩阵
        for (int i = 0;i < citys;i++)
            for (int j = i+1; j < citys; j++)
                if (citysConnexted[i][j] == 1) merge(i,j,head,level);//如果相邻就合并

        // 查有多少个省份
        int count = 0;
        for (int i = 0; i < citys; i++)
            if (head[i] == i) count++;

        return count;
    }

    // 合并
    private static void merge(int x,int y,int[] head,int[] level) {
        int i = find(x,head);
        int j = find(y,head);

        if (i == j) return;//根节点一样，不用合并

        // 合并，矮树往高树上合并
        if (level[i] <= level[j]) head[i] = j;
        else head[j] = i;

        if (level[i] == level[j]) {
            level[i]++;
            level[j]++;
        }
    }

    private static int find(int x, int[] head) {
        if (head[x] == x) return x;//自己就是根节点
        head[x] = find(head[x],head);   //修改根节点
        return head[x];
    }
}
